package pers.qianyu.month_202101.date_20210125;

/**
 * 剑指 Offer 16. 数值的整数次方
 * https://leetcode-cn.com/problems/shu-zhi-de-zheng-shu-ci-fang-lcof/submissions/
 * - 快速幂
 *
 * @author mizzle rain
 * @date 2021-01-25 13:02
 */
public class MyPow {
    public double myPow(double x, int n) {
        if (x == 0) return 0;
        long b = n;
        // 注意，将n装换为long类型必须在 b = -b前面，防止题目卡int的边界
        if (b < 0) {
            b = -b;
            x = 1 / x;
        }
        double res = 1.0;
        while (b > 0) {
            if ((b & 1) == 1) res *= x;
            x *= x;
            b >>= 1;
        }
        return res;
    }
}
